#pragma once

#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <string>
#include<cassert>
#include"bitsutil.h"

template<uint32_t bitsPreTag>
class SingleTable {
  // 每一个 Bucket 有多少的Tags
  static const uint32_t kTagsPerBucket = 4;
  static const uint32_t kBytesPerBucket = (bitsPreTag * kTagsPerBucket + 7) >> 3;
  static const uint32_t kTagMask = (1ULL << bitsPreTag) - 1;

  // 根据每一个 Bucket 的大小，设置边界的Bucket 的数量
  static const uint32_t kPaddingBuckets = ((kBytesPerBucket + 7) / 8 * 8 - 1) / kBytesPerBucket;

  struct Bucket {
	char bits_[kBytesPerBucket];
  } __attribute__((__packed__));//取消结构体内存对齐

  // 创建保存Bucket实例的指针
  Bucket *buckets_;
  // Buckets 个数
  uint32_t numBuckets_;

 public:
  explicit SingleTable(const uint32_t num)
	  : numBuckets_(num) {
	// 分配内存
	buckets_ = new Bucket[numBuckets_ + kPaddingBuckets];
	// 初始化内存
	memset(buckets_, 0, kBytesPerBucket * (numBuckets_ + kPaddingBuckets));
  }
  ~SingleTable() {
	delete[] buckets_;
  }
  // 返回当前 有效的Buckets 的数量，不包括Padding Bucket
  uint32_t NumBuckets() const {
	return numBuckets_;
  }
  // 返回整个 Table 中，所有有效的 Bucket 所占的内存字节
  uint32_t SizeInBytes() const {
	return kBytesPerBucket * numBuckets_;
  }

  // 返回整个 Table 中 Tag 的数量
  uint32_t SizeInTags() const {
	return kTagsPerBucket * numBuckets_;
  }

  // 输出 Table 相关信息
  std::string Info() const {
	std::stringstream ss;
	ss << "SingleHashtable with tag size: " << bitsPreTag << " bits \n";
	ss << "\t\tAssociativity: " << kTagsPerBucket << "\n";
	ss << "\t\tTotal # of rows: " << numBuckets_ << "\n";
	ss << "\t\tTotal # slots: " << SizeInTags() << "\n";
	return ss.str();
  }

  // 从p[i,j] 中读取 tag
  inline uint32_t ReadTag(const uint32_t i, const uint32_t j) const {
	const char *p = buckets_[i].bits_;
	uint32_t tag;

	switch (bitsPreTag) {
	  case 2: {
		tag = *((uint8_t *)(p)) >> (j * 2);
		break;
	  }
	  case 4: {
		p += (j >> 1);
		tag = *((uint8_t *)(p)) >> ((j & 1) << 2);
	  }
	  case 8: {
		p += j;
		tag = *((uint8_t *)(p));
		break;
	  }
	  case 12: {
		p += j + (j >> 1);
		tag = *((uint16_t *)(p)) >> ((j & 1) << 2);
		break;
	  }
	  case 16: {
		p += (j << 1);
		tag = *(uint16_t *)p;
		break;
	  }
	  case 32: {
		tag = ((uint32_t *)p)[j];
		break;
	  }
	  default: break;
	}
	return tag & kTagMask;
  }

  // 在p[i,j] 对应的 tag 写入值
  inline void WriteTag(const uint32_t i, const uint32_t j, const uint32_t t) {
	char *p = buckets_[i].bits_;
	uint32_t tag = t & kTagMask;

	switch (bitsPreTag) {
	  case 2: {
		*((uint8_t *)p) |= tag << (2 * j);
		break;
	  }
	  case 4: {
		p += (j >> 1);
		if (j & 1) {
		  *((uint8_t *)p) &= 0x0f;
		  *((uint8_t *)p) |= tag;
		} else {
		  *((uint8_t *)p) &= 0xf0;
		  *((uint8_t *)p) |= (tag << 4);
		}
		break;
	  }
	  case 8: {
		((uint8_t *)p)[j] = tag;
		break;
	  }
	  case 12: {
		p += (j + (j >> 1));
		if (j & 1) {
		  ((uint16_t *)p)[0] &= 0x000f;
		  ((uint16_t *)p)[0] |= (tag << 4);
		} else {
		  ((uint16_t *)p)[0] &= 0xf000;
		  ((uint16_t *)p)[0] |= tag;
		}
		break;
	  }
	  case 16: {
		((uint16_t *)p)[j] = tag;
		break;
	  }
	  case 32: {
		((uint32_t *)p)[j] = tag;
		break;
	  }
	  default: break;
	}
  }

  // 在第 i 个 Buckets 里面寻找 tag
  bool FindTagInBuckets(const uint32_t i, const uint32_t tag) const {
	if (kTagsPerBucket == 4) {
	  const char *p = buckets_[i].bits_;
	  uint64_t v = *((uint64_t *)p);
	  switch (bitsPreTag) {
		case 4: return hasvalue4(v, tag);
		case 8: return hasvalue8(v, tag);
		case 12: return hasvalue12(v, tag);
		case 16 :return hasvalue16(v, tag);
		default: break;
	  }
	}

	for (uint32_t j = 0; j < kTagsPerBucket; j++) {
	  if (ReadTag(i, j) == tag) {
		return true;
	  }
	}
	return false;
  }

  // FindTagInBuckets 第二个版本，在 i,j 两个 Bucket 里面寻找 目标
  bool FindTagInBuckets(const uint32_t i, const uint32_t j, const uint32_t tag) {
	return FindTagInBuckets(i, tag) || FindTagInBuckets(j, tag);
  }

  // 从第 i 个Bucket 中删除对应的 tag
  bool DeleteTagFromBucket(const size_t i, const uint32_t tag) {
	for (uint32_t j = 0; j < kTagsPerBucket; j++) {
	  if (ReadTag(i, j) == tag) {
		assert(FindTagInBuckets(i, tag) == true);
		WriteTag(i, j, 0); //在对应的位置上写入 0  既删除对应的数据
		return true;
	  }
	}
	return false;
  }

  // 向第 i 个Bucket 中没有被写入的 Tag 中写入数据
  bool InsertTagToBucket(const uint32_t i, const uint32_t tag, const bool kickOut, uint32_t &oldTag) {
	for (uint32_t j = 0; j < kTagsPerBucket; j++) {
	  if (ReadTag(i, j) == 0) {
		WriteTag(i, j, tag);
		return true;
	  }
	}

	// 如果发生了挤兑
	if (kickOut) {
	  uint32_t r = random() % kTagsPerBucket;
	  oldTag = ReadTag(i, r); //把原来的数据挤兑出去
	  WriteTag(i, r, tag); // 写入新的数据
	}
	return false;
  }

  // 返回第 i 个Bucket中Tag的数量
  uint32_t NumTagsInBucket(const uint32_t i) const {
	uint32_t num = 0;
	for (uint32_t j = 0; j < kTagsPerBucket; j++) {
	  if (ReadTag(i, j) != 0) {
		num++;
	  }
	}
	return num;
  }
};



